package com.lft.search03.insert_value_search;

import java.util.ArrayList;
import java.util.List;

/**
 * 插值查找算法
 */
public class InsertValueSearch {
	public static void main(String[] args) {
		int[] a = new int[100];
		for (int i = 0; i < 100; i++) {
			a[i] = i + 1;
		}
		List insertValueSearch = insertValueSearch(a, 0, a.length - 1, 1);
		if (insertValueSearch.size() == 0) {
			System.out.println("没有找到");
		} else {
			System.out.println("找到了，索引是：" + insertValueSearch);
		}
		
	}
	
	/**
	 * @param a     原始数组(有序数组)
	 * @param left  左索引
	 * @param right 右索引
	 * @param value 要查找的值
	 * @return 返回所有查找到的索引，没有找到就返回空集合。
	 */
	public static List<Integer> insertValueSearch(int[] a, int left, int right, int value) {
		// System.out.println("====");
		// 必须校验。防止下面的 mid 下标越界。
		if (left > right || value < a[0] || value > a[a.length - 1]) {
			return new ArrayList<Integer>();
		}
		int mid = left + (right - left) * (value - a[left]) / (a[right] - a[left]);
		int midValue = a[mid];
		// 向左递归查找
		if (value < midValue) {
			return insertValueSearch(a, left, mid - 1, value);
		}
		// 向右递归查找
		else if (value > midValue) {
			return insertValueSearch(a, mid + 1, right, value);
		}
		// 相等
		else {
			List list = new ArrayList();
			// 往左查找，看是否还有相同的值。
			int temp = mid - 1;
			while (true) {
				// 遍历，当 temp 小于 0，或者 a[temp] != value 时跳出循环。
				if (temp < 0 || a[temp] != value) {
					break;
				}
				// 将找到的索引 加入 集合。
				list.add(temp);
				// 再向左移一位。
				temp--;
			}
			// 把原先查找到的索引 加入 集合。
			list.add(mid);
			// 往右查找，看是否还有相同的值。
			temp = mid + 1;
			while (true) {
				// 遍历，当 temp 大于 数组长度，且 a[temp] != value 时跳出循环。
				if (temp > a.length || a[temp] != value) {
					break;
				}
				// 将找到的索引 加入 集合。
				list.add(temp);
				// 再向右移一位。
				temp++;
			}
			// 返回集合。
			return list;
		}
	}
}
